/*
 * =====================================================================================
 *
 *       Filename:  ListProblem.cpp
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  2011-10-26 9:44:26
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *        Company:
 *
 * =====================================================================================
 */

#include "ListProblem.h"
#include "gtest/gtest.h"

#define LIST_TEST_COUNT 100

//isListLoop test noLoop
TEST(isListLoop, noLoop)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createList<int>(n);
        EXPECT_TRUE(isListLoop(head) == false);
        deleteList(head);
    }
}

//isListLoop test haveLoop
TEST(isListLoop, haveLoop)
{
    for (int n = 1; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createLoopList<int>(n);
        EXPECT_TRUE(isListLoop(head) == true);
        deleteList(head);
    }
}

//测试计算带环链表的环的长度
TEST(loopLenListLoop, Loop)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        for (int entry = 0; entry < n; ++entry) {
            ListNode<int> *headLoop = createLoopList<int>(n, entry);
            EXPECT_TRUE(loopLenListLoop(headLoop) == n - entry);
            deleteLoopList(headLoop);
        }
    }
}

//测试带环链表的入口节点
TEST(entryLoopList, mustHaveLoop)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        for (int entry = 0; entry < n; ++entry) {
            ListNode<int> *head = createLoopList<int>(n, entry);
            ListNode<int> *pentry = entryLoopList(head);
            EXPECT_TRUE(pentry->element == entry);
            deleteLoopList(head);
        }
    }
}

//测试计算带环链表的长度
TEST(lenListLoop, mustHaveLoop)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        for (int entry = 0; entry < n; ++entry) {
            ListNode<int> *head = createLoopList<int>(n, entry);
            EXPECT_TRUE(lenListLoop(head) == n);
            deleteLoopList(head);
        }
    }
}

//测试 判断两个链表是否相交
TEST(isTwoListCross, noLoopOrHaveLoop)
{
    //创建三条链表
    //将其中两条链表连接到第三条链表上
    //从而形成相交链表
    const int cnt = 20;

    for (int n1 = 1; n1 <= cnt; ++n1) {
        for (int n2 = 1; n2 <= cnt; ++n2) {
            for (int n3 = 1; n3 <= cnt; ++n3) {
                //创建链表
                ListNode<int> *head1 = createList<int>(n1);
                ListNode<int> *head2 = createList<int>(n2);
                ListNode<int> *head3 = createList<int>(n3);

                //连接链表
                ListNode<int> *end1 = head1;

                while (end1 && end1->next) {
                    end1 = end1->next;
                }

                ListNode<int> *end2 = head2;

                while (end2 && end2->next) {
                    end2 = end2->next;
                }

                end1->next = head3;
                end2->next = head3;

                //进行测试
                EXPECT_TRUE(isTwoListCross(head1, head2) == true);

                //断开连接
                end1->next = NULL;
                end2->next = NULL;

                //进行测试
                EXPECT_TRUE(isTwoListCross(head1, head2) == false);

                //删除链表
                deleteList(head1);
                deleteList(head2);
                deleteList(head3);
            }
        }
    }
}

//测试两条相交链表的交点
TEST(crossOfTwoList, mustHaveCross)
{
    //创建三条链表
    //将其中两条链表连接到第三条链表上
    //从而形成相交链表
    const int cnt = 20;

    for (int n1 = 1; n1 <= cnt; ++n1) {
        for (int n2 = 1; n2 <= cnt; ++n2) {
            for (int n3 = 1; n3 <= cnt; ++n3) {
                //创建链表
                ListNode<int> *head1 = createList<int>(n1);
                ListNode<int> *head2 = createList<int>(n2);
                ListNode<int> *head3 = createList<int>(n3);

                //连接链表
                ListNode<int> *end1 = head1;

                while (end1 && end1->next) {
                    end1 = end1->next;
                }

                ListNode<int> *end2 = head2;

                while (end2 && end2->next) {
                    end2 = end2->next;
                }

                end1->next = head3;
                end2->next = head3;

                //进行测试
                EXPECT_TRUE(crossOfTwoList(head1, head2) == head3);

                //断开连接
                end1->next = NULL;
                end2->next = NULL;

                //删除链表
                deleteList(head1);
                deleteList(head2);
                deleteList(head3);
            }
        }
    }
}

//测试链表反转
TEST(reverseList, noLoop)
{
    for (int n = 1; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createList<int>(n);
        ListNode<int> *newHead = reverseList(head);
        EXPECT_TRUE(newHead->element == n - 1);

        while (newHead->next) {
            newHead = newHead->next;
        }

        EXPECT_TRUE(newHead->element == 0);
        deleteList(head);

        ListNode<int> *head2 = createList<int>(n);
        ListNode<int> *newHead2 = reverseList(head2);
        EXPECT_TRUE(newHead2->element == n - 1);

        while (newHead2->next) {
            newHead2 = newHead2->next;
        }

        EXPECT_TRUE(newHead2->element == 0);
        deleteList(head2);
    }
}

//测试 找到单链表倒数第K个节点
TEST(findReversalKnode, noLoop)
{
    for (int n = 1; n < LIST_TEST_COUNT; ++n) {
        for (int k = 1; k <= n; ++k) {
            ListNode<int> *head = createList<int>(n);
            EXPECT_TRUE(findListElement(head, n - k) == findReversalKnode(head, k));
            EXPECT_TRUE(findMidNode(head) == findListElement(head, (n + 1) / 2 - 1));
        }
    }
}

//测试 链表加法运算
TEST(addImpWithList, noLoop)
{
    for (int m = 2; m < LIST_TEST_COUNT; ++m) {
        for (int n = 1; n < m; ++n) {
            ListNode<int> *head1 = createList<int>(m);
            ListNode<int> *head2 = createList<int>(n);
            ListNode<int> *head3 = NULL;
            addImpWithList(head1, m, head2, n, head3);

            int h1 = 0;

            while (head1) {
                h1 = h1 * 10 + head1->element;
                head1 = head1->next;
            }

            int h2 = 0;

            while (head2) {
                h2 = h2 * 10 + head2->element;
                head2 = head2->next;
            }

            int h3 = 0;

            while (head3) {
                h3 = h3 * 10 + head3->element;
                head3 = head3->next;
            }

            EXPECT_TRUE(h1 + h2 == h3);

            deleteList(head1);
            deleteList(head2);
            deleteList(head3);
        }
    }
}

//测试 合并有序链表
TEST(merageList, noCross)
{
    for (int n = 1; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head1 = createList<int>(n, 1, 4);
        ListNode<int> *head2 = createList<int>(n, 2, 3);
        ListNode<int> *head3 = merageList(head1, head2, std::less_equal<int>());

        ListNode<int> *p = head3;

        while (p->next) {
            EXPECT_TRUE(p->element <= p->next->element);
            p = p->next;
        }

        deleteList(head3);
    }
}

//测试 合并相交的有序链表
TEST(merageCrossList, haveCross)
{
    for (int n = 1; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head1 = createList<int>(n, 1, 4);
        ListNode<int> *head2 = createList<int>(n, 2, 3);
        ListNode<int> *head3 = createList<int>(n, 100000, 3);
        //连接链表
        ListNode<int> *end1 = head1;

        while (end1 && end1->next) {
            end1 = end1->next;
        }

        ListNode<int> *end2 = head2;

        while (end2 && end2->next) {
            end2 = end2->next;
        }

        end1->next = head3;
        end2->next = head3;

        ListNode<int> *head4 = merageCrossList(head1, head2, std::less_equal<int>());
        ListNode<int> *p = head4;

        while (p->next) {
            EXPECT_TRUE(p->element <= p->next->element);
            p = p->next;
        }

        deleteList(head4);
    }
}

//测试 两个有序链表的交集
TEST(intersectionOfTwoOrderedList, ordered)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head1 = createList<int>(n, 3, 1);
        ListNode<int> *head2 = createList<int>(n, 1, 2);
        ListNode<int> *interHead = intersectionOfTwoOrderedList(head1, head2);
        ListNode<int> *p = interHead;

        while (p) {
            EXPECT_TRUE(findListElement(head1, p->element) != NULL);
            EXPECT_TRUE(findListElement(head2, p->element) != NULL);
            p = p->next;
        }

        deleteList(head1);
        deleteList(head2);
        deleteList(interHead);
    }
}


//测试 单链表冒泡排序
TEST(bubbleSortList, randList)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createRandList<int>(n);
        head = bubbleSortList(head);
        EXPECT_TRUE(countList(head) == n);
        EXPECT_TRUE(isListGreatOrder(head) == true);
        deleteList(head);
    }
}

//测试 单链表选择排序
TEST(selectSortList, randList)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createRandList<int>(n);
        head = selectSortList(head);
        EXPECT_TRUE(countList(head) == n);
        EXPECT_TRUE(isListGreatOrder(head) == true);
        deleteList(head);
    }
}

//测试 单链表插入排序
TEST(insertSortList, randList)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createRandList<int>(n);
        head = insertSortList(head);
        EXPECT_TRUE(countList(head) == n);
        EXPECT_TRUE(isListGreatOrder(head) == true);
        deleteList(head);
    }
}

//测试 单链表快速排序
TEST(quickSortList, randList)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createRandList<int>(n);
        head = quickSortList(head);
        EXPECT_TRUE(countList(head) == n);
        EXPECT_TRUE(isListGreatOrder(head) == true);
        deleteList(head);
    }
}

//测试 单链表归并排序 自顶向下
TEST(mergeSortList, randList)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createRandList<int>(n);
        head = mergeSortList(head);
        EXPECT_TRUE(countList(head) == n);
        EXPECT_TRUE(isListGreatOrder(head) == true);
        deleteList(head);
    }
}

//测试 单链表归并排序 自底向上
TEST(mergeSortListBU, randList)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createRandList<int>(n);
        head = mergeSortListBU(head);
        EXPECT_TRUE(countList(head) == n);
        EXPECT_TRUE(isListGreatOrder(head) == true);
        deleteList(head);
    }
}

//测试 删除无序单链表重复元素
TEST(deleteDupKeys, randList)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createRandList<int>(n);
        head = deleteDupKeys(head);
        EXPECT_TRUE(isHaveDupKeys(head) == false);
        deleteList(head);
    }

    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createRandList<int>(n);
        head = deleteDupKeysUseSort(head);
        EXPECT_TRUE(isHaveDupKeys(head) == false);
        deleteList(head);
    }
}

//测试 删除无序单链表重复元素
TEST(deleteDupKeys, singleList)
{
    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createSingleList<int>(n);
        head = deleteDupKeys(head);
        EXPECT_TRUE(isHaveDupKeys(head) == false);
        deleteList(head);
    }

    for (int n = 0; n < LIST_TEST_COUNT; ++n) {
        ListNode<int> *head = createSingleList<int>(n);
        head = deleteDupKeysUseSort(head);
        EXPECT_TRUE(isHaveDupKeys(head) == false);
        deleteList(head);
    }
}

int main(int argc, char *argv[])
{
    testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
